import java.util.HashMap;
import java.util.Map;
import java.util.Random;

public class CopyNode {
    /*public Node copyRandomList(Node head) {
        if (head == null) {
            return head;
        }
        Map<Node, Node> map = new HashMap<Node, Node>();
        Node newHead = head;
        Node dummy = new Node(-1);
        while (newHead != null) {
            Node newNode;
            if (!map.containsKey(newHead)) {
                newNode = new Node(newHead.val);
                map.put(newHead, newNode);
            } else {
                newNode = map.get(newHead);
            }
            dummy.next = newNode;
            if (newHead.random != null) {
                Node random = newHead.random;
                if (map.containsKey(random)) {
                    Node copyRandom = map.get(random);
                    newNode.random = copyRandom;
                } else {
                    Node copyRandom = new Node(random.val);
                    map.put(random, copyRandom);
                    newNode.random = copyRandom;
                }
            }
            dummy = newNode;
            newHead = newHead.next;
        }
        return map.get(head);
    }*/

    public  Node  copyRandomList(Node head){
        if (head == null){
            return head;
        }
        HashMap<Node, Node> map = new HashMap<>();
        Node newHead =head;
        Node nextNode = new Node(-1);
        while (newHead!=null){
            Node copyNewHead;
            //使用map为了处理指针指向自己的情况
            if (!map.containsKey(newHead)){
               //复制容器
                copyNewHead =new Node(newHead.val);
                map.put(newHead,copyNewHead);
            }else {
                copyNewHead = map.get(newHead);
            }
            //next指针
            nextNode.next = copyNewHead;
            //复制随机指针random
            if (newHead.random != null){
                Node random =newHead.random;
                if (map.containsKey(random)){
                   Node copyRandom =map.get(random);
                   //copy
                    copyNewHead.random =copyRandom;
                }else{
                    //放map中copy
                    Node copyRandom = new Node<>(random.val);
                    map.put(random,copyRandom);
                    //copy
                    copyRandom.random=copyRandom;
                }
            }
            //初始化+迭代
            nextNode=copyNewHead;
            newHead =newHead.next;
        }
        return map.get(head);
    }
    public static void main(String[] args) {
        // 构造原始链表
        Node node1 = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(3);

        node1.next = node2;
        node2.next = node3;
        node1.random = node3;  // 1->3
        node2.random = node1;  // 2->1
        node3.random = node2;  // 3->2

        // 执行深拷贝
        CopyNode copier = new CopyNode();
        Node copiedHead = copier.copyRandomList(node1);

        // 验证拷贝结果
        System.out.println("Original vs Copy:");
        printComparison(node1, copiedHead);
    }
    private static void printComparison(Node original, Node copy) {
        while (original != null && copy != null) {
            System.out.printf("Val: %d (orig:%d) | ",
                    copy.val, original.val);
            System.out.printf("Next: %s (orig:%s) | ",
                    copy.next != null ? copy.next.val : "null",
                    original.next != null ? original.next.val : "null");
            System.out.printf("Random: %s (orig:%s)%n",
                    copy.random != null ? copy.random.val : "null",
                    original.random != null ? original.random.val : "null");

            original = original.next;
            copy = copy.next;
        }
    }
}
